package leetcode.day;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

// 382. 链表随机节点
public class Solution {
    List<Integer> list = new ArrayList<>();
    Random random = new Random(20220116);

    //放到集合中，然后随机访问集合
    public Solution(ListNode head) {
        ListNode tmp = head;
        while (tmp != null) {
            list.add(tmp.val);
            tmp = tmp.next;
        }


    }

    public int getRandom() {
        int index = random.nextInt(list.size());
        return list.get(index);
    }

}


// 蓄水池抽样法
class Solution2 {

    Random random;
    ListNode head;

    //放到集合中，然后随机访问集合
    public Solution2(ListNode head) {
        this.head = head;
        this.random = new Random();
    }

    public int getRandom() {
        int reserve = 0;
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            int r = this.random.nextInt(count) + 1;
            if (r == count) {
                reserve = cur.val;
            }
            cur = cur.next;
        }
        return reserve;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

